#! /usr/bin/env python
# -*- coding: utf-8 -*-

# *************************************************************
#     Filename @  binary_search.py
#       Author @  Huoty
#  Create date @  2016-06-14 16:12:18
#  Description @  
# *************************************************************

def binary_search_recursion(lst, value, low, high):  
    if high < low:  
        return None
    mid = (low + high) / 2  
    if lst[mid] > value:  
        return binary_search_recursion(lst, value, low, mid-1)  
    elif lst[mid] < value:  
        return binary_search_recursion(lst, value, mid+1, high)  
    else:  
        return mid  

def binary_search_loop(lst,value):  
    low, high = 0, len(lst)-1  
    while low <= high:  
        mid = (low + high) / 2  
        if lst[mid] < value:  
            low = mid + 1  
        elif lst[mid] > value:  
            high = mid - 1
        else:
            return mid  
    return None
    
def binary_search_bisect(lst, x):
    from bisect import bisect_left
    i = bisect_left(lst, x)
    if i != len(lst) and lst[i] == x:
        return i
    return None

def binary_search_npsearch(lst, x):
    from numpy import searchsorted
    i = searchsorted(lst, x)
    if i != len(lst) and lst[i] == x:
        return i
    return None

  
# Script starts from here

if __name__ == "__main__":
    import random
    lst = [random.randint(0, 10000) for _ in xrange(100000)]
    lst.sort()
    
    def test_recursion():
        binary_search_recursion(lst, 999, 0, len(lst)-1)

    def test_loop():
        binary_search_loop(lst, 999)
        
    def test_bisect():
        binary_search_bisect(lst, 999)

    def test_npsearch():
        binary_search_npsearch(lst, 999)
    
    import timeit
    t1 = timeit.Timer("test_recursion()", setup="from __main__ import test_recursion")
    t2 = timeit.Timer("test_loop()", setup="from __main__ import test_loop")
    t3 = timeit.Timer("test_bisect()", setup="from __main__ import test_bisect")
    t4 = timeit.Timer("test_npsearch()", setup="from __main__ import test_npsearch")

    print "Recursion:", t1.timeit()
    print "Loop:", t2.timeit()
    print "Bisect:", t3.timeit()
    print "NPSearch:", t4.timeit(number=100)

